⟸ Go Back ⟸
Exercise 1 (Homework 4).
(context-free languages, pumping lemma)

Just context-free, or actually regular?

Later in the course we will see that no algorithm exists that always terminates and gives the answer to the question “Given a context-free grammar, does it generate a regular language?”.

For each of the context-free grammars below, find what is the language generated and prove whether it is a regular language or not.

  1. \left\{\begin{array}{ccl} S &\to& AB \mid CD \\ A &\to& 0A0 \mid 0 \\ B &\to& 1B1 \mid \lambda \\ C &\to& 0C0 \mid \lambda \\ D &\to& 1D1 \mid \lambda \end{array}\right.
  2. \left\{\begin{array}{ccl} S &\to& aA \mid bB \mid \lambda \\ A &\to& Sa \mid Sb \\ B &\to& Sb \end{array}\right.
  3. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 1 \\ B &\to& 1B1 \mid 0 \end{array}\right.
  4. \left\{\begin{array}{ccl} S &\to& 0S0 \mid 0S1 \mid \lambda \end{array}\right.
  5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 0A1 \mid \lambda \\ B &\to& 0B \mid 1B \mid \lambda \end{array}\right.
  6. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0S0 \mid 1S1 \mid \lambda \\ B &\to& 0S1 \mid 1S0 \mid \lambda \end{array}\right.
  7. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0A0 \mid 1A1 \mid \lambda \\ B &\to& 0B1 \mid 1B0 \mid \lambda \end{array}\right.
  8. \left\{\begin{array}{ccl} S &\to& aSa \mid bSb \mid X \\ X &\to& aXb \mid bXa \mid a \mid b \mid \lambda \end{array}\right.
  9. \left\{\begin{array}{ccl} S &\to& WXW' \\ X &\to& aX \mid bX \mid \lambda \\ W &\to& aW \mid bW \mid \lambda \\ W' &\to& W'a \mid W'b \mid \lambda \end{array}\right.